package com.killer.linear;

/**
 * 链表集合
 */
public class MyLinkedList<T> implements MyList<T> {

    /**
     * 头结点
     */
    private Node<T> head;

    /**
     * 集合大小
     */
    private int size=0;

    public void add(T t) {
        size++;
        Node<T> node = new Node<T>(t);
        if (head == null) {
            //如果头节点为空,则直接将该节点赋给头结点
            head=node;
            return;
        }
        Node<T> tmp=head;
        //一直找到最后一个节点
        while (tmp.next != null) {
            tmp=tmp.next;
        }
        //将该节点挂载到最后一个节点的next处
        tmp.next=node;
    }

    public void set(int index, T t) {
        if (index > size - 1) {
            throw new RuntimeException("数组下标越界了");
        }
        size++;
        Node<T> node = new Node<T>(t);
        //判断是否是在头结点插入
        if (index == 0) {
            node.next=head;
            head=node;
            return;
        }
        //前一个节点
        Node<T> preNode = getNode(index - 1);
        //原来的此处的节点
        Node<T> oldNode = getNode(index);
        preNode.next=node;
        node.next=oldNode;
    }

    private Node<T> getNode(int index) {
        Node<T> tmp=head;
        for(int i=0;i<index;i++) {
            //0代表头结点,index是多少就往下找多少层
            tmp=tmp.next;
        }
        return tmp;
    }

    public int size() {
        return size;
    }

    public void traverse() {
        Node<T> tmp=head;
        //从头节点一直往下遍历
        while (tmp != null) {
            System.out.println(tmp.data);
            tmp=tmp.next;
        }
    }

    public T get(int index) {
        return getNode(index).data;
    }

    public void remove(int index) {
        if (index > size - 1) {
            throw new RuntimeException("数组下标越界了");
        }
        size--;
        //是否是删除头结点
        if (index == 0) {
            //头结点指向头结点的下一个节点
            head=head.next;
            return;
        }
        //是否是删除最后一个节点
        if (index == size - 1) {
            //倒数第二个节点指向空
            getNode(index-1).next=null;
            return;
        }
        //前一个节点直接指向后一个节点
        getNode(index - 1).next = getNode(index + 1);
    }

    private class Node<T>{
        /**
         * 数据域
         */
        T data;

        /**
         * 指针域
         */
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }
}
